COMMENT ⊗   VALID 00013 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	PROPOSAL TO NSF  - RANN -  (Bernie Chern).
C00004 00003	1. IDEAS AND WORK ALREADY DONE.
C00007 00004	iv. Object Representation from Physical Measurement,
C00008 00005	v. Mechanical Simulation.
C00009 00006	2. PREVIOUS WORK AT STANFORD.
C00012 00007	3. RELATION TO WORK DONE ELSEWHERE.
C00013 00008	4. FACILITIES AT STANFORD A.I. LAB
C00014 00009	5. WHAT WE PROPOSE TO DO.
C00016 00010	 Elements of a Geometric Modeling System.
C00018 00011	   Five Version of a Geometric Modeling System.
C00019 00012	   Itemize Shopping List.
C00023 00013	6. BUDGET
C00024 ENDMK
C⊗;
PROPOSAL TO NSF  - RANN -  (Bernie Chern).

	Principle Investigator - John McCarthy.
	Co Principle Investigator - Bruce Baumgart.

	This is a request for a grant of XXX to support
a two year research program in computer aided mechanical
drawing of three dimensional objects.


OUTLINE
	1. Ideas and work already done.
	2. Previous work at Stanford.
	3. Relation to work done elsewhere.
	4. Facilities at Stanford AI Lab.
	5. What we propose to do.
	6. Budget.


1. IDEAS AND WORK ALREADY DONE.

	The proposed work  is based on  the following ideas  and work
already done:

i. Explicit Object Representation.

	An effective way  of obtaining drawings of  three dimensional
objects is  to derive the drawing from  an explicit computer model of
the  three  dimensional  object.  The  orthographic,  isometric   and
perspective  projections of  the objects  are obtained  automatically
from the  three dimensional description; with the hidden lines of the
object either  eliminated, dashed  or thinned; and with the  appropriate
labels,  dimensions,  comments,  and  arrowheads  indicated.

ii. Object Representation from Logical Description.

	One convenient  way of making  an explicit computer  model of
an object is  to simulate the process of building the object; that is
the  description  of   how  to  build  an   object  is  an   implicit
representation of the  object.  For example it is  more convenient to
describe  Figure-1  implicitly as  a unit  cube  with a  regular five
pointed half unit star shaped hole through it; than as  a list of the
locii  of all  the vertices;  and the  detailed specification  of the
face, edge  and vertex  linkages; or  worse yet  having to  draw  the
object with a light pen.

iii. Model Building Primitives.

	The simulated object building process

iv. Object Representation from Physical Measurement,

	Another way getting an explicit computer model is to derive it
from measurements made on an actual physical object, 2D drawings, or
pictures. The physical object might be a clay or wood model of the thing
begin designed. We propose that a three dimensional object stereotype can
be accurately entered into a computer by means of a television camera
v. Mechanical Simulation.

	Dynamic information such as the degrees of freedom of motion are
included in the object description and can be used to get pictures of the
objects in different positions. Moves of a mechanical arm design involving
vi. Photomeric Simulation.
vii. Robotics.
2. PREVIOUS WORK AT STANFORD.

	This proposal is based on work by Bruce G. Baumgart as a
graduate student. Mr. Baumgart expects to complete his
dissertation entitled "Geometric Vision" in December 1973 and
will continue as a research associate on receiving his degree.

	This work includes GEOMED, a Geometric Editor, which would
is the prototype of the mechanical drawing system we propose to build.
GEOMED is a 3D drawing  program accessed thru a one character
jump  table.  GEOMED  can construct arbitrary  polyhedral objects and
display them with  hidden lines eliminated.   GEOMED can also  accept
CRE's  perceived images and  form a polyhedral world model consistent
with such images.

	GEOMEL is the bulk of GEOMED  embedded in a LISP core  image.
That is  the  subroutines comprising  Geomed are  accessible in  LISP
notation,   thus  providing a geometric  language for  physical world
modeling and physical action simulation.

	GEOMES is the bulk of  GEOMED embedded in a SAIL core  image.
That is the subroutines comprising GEOMED become SAIL accessible.

	TVFONT is  for making  type font  bit arrays from  television
images, or for rescaling existing fonts.

	CRE   is  converts a  sequence of  digital  television images
into a video intensity contour data structure. Auxiliary  routines of
CRE  provide cart and turntable control and XGP video output.

3. RELATION TO WORK DONE ELSEWHERE.

4. FACILITIES AT STANFORD A.I. LAB

	1. Time Sharing System - its relevance.
	2. III displays
	3. Data Disc displays.
	4. XGP printer
	5. Output for FR-80.

5. WHAT WE PROPOSE TO DO.

	We  propose to  represent  and simulate  solid  objects in  a
computer for  the sake of mechanical design,   mechanical drawing and
robotics.  Our two year goal will be to automate as much  as possible
the task of  creating and altering three  dimensional data structures
from  which mechanical drawings can be  derived; this work would also
be  a step  towards  solving  the problem  of  representing  physical
objects for  a robot.   The overall project  to date has  been called
"geometric modeling" a term which we  use to refer to our  particular
combination  of computer  graphics,  physical world  modeling,  image
processing  and geometry.   Accordingly, the  details of the  work we
propose doing will be presented  in terms of the elements  comprising
a  Geometric  Modeling System,  GMS,  and  in  terms of  the  several
versions  of such a system  that we believe  necessary or possible to
build. (The  reader interested only  in an  itemized list of  project
goals is advice to skip to the end of this section).
 Elements of a Geometric Modeling System.

	Like  a computer,  the  four  main  elements of  a  geometric
modeling system are  memory, process, input and output. Starting with
memory, there are the problems  of representation (how to describe  a
physical object); accessing (how to  find a particular description by
name,  by  location, or  by  whether it  is currently  in  view); and
efficiency (how to  keep the size  of storage space  down and how  to
dynamically allocate fast and slow memory resources).
	
	As  mention  before,    our  GMS has  explicit  and  implicit
representations.  The  presently implemented explicit  representation
is based  on polyhedron  models of  solid rigids  objects.  A  simple
object called  a body is defined be  surface shell composed of faces,
edges and vertices (that satisfy the Euler  equation V - E + F =  2);
such polyhedron bodies  are combined to form compounded  objects.  At
present a  simple curved object is represented by approximating it to
the desired  accuracy with  a polyhedron composed  of flat  polygonal
faces. We propose elabor
   Five Version of a Geometric Modeling System.

	1. Present version. 1973-1974.
		Polyhedron based modeling.
	2. Intermediate version. 1974-1975.
		Manifold based modeling.
	3. Advanced version. 1975.
		Mechanical simulation.
		Photometric simulation.
	4. Standard version. FORTRAN.
	5. Small Machine Version. PDP-11.

   Itemize Shopping List.

	Ignoring the overall system organization and fine details,
the goals of the proposed project are summarized in the following
shopping list:


Items partially in hand.

	1. Representation of solid rigid three dimensional polyhedra.
	2. Language extension of geometric primitives.
	3. Language extension of object building primitives.
	4. Polyhedron object hidden line eliminator.
	5. Geometric editor.

Items within one year's work.
	
	6. Generation of ordinary mechanical drawings from geometric models.
	7. Representation for curved objects.
	8. Representation for flexible objects.
	9. Video acquisition of two dimensional  drawings.
	10. Mechanical simulation and animation.

Second Year and Elective Items.

	11. Generation of high quality mechanical drawings, such as
		assembly drawings and cut away layout drawings.
	12. Development of a remote display terminal version of the system.
	13. Development of a standard FORTRAN version of a subset of the system.
	14. Mechanical drawings for a special area of engineering;
	    (pipefitting, screw threading, mining, or whatever).

Basic research items.

	15. Video acquisition of three dimensional objects.
	16. Photometric simulation - shadows, multiple light sources, etc.
	      generation of high quality video appearance.


	To elaborate, substantial  work has already been done  on the
first   five  items  listed;   so  that  the   most  pessimistic  and
conservative estimate of  our potential  achivevements over the  next
two  years   should  include   the  documentation,   publication  and
elaboration  of  the research  work  already done.  Our intermediate
expectations  include  making   considerable  progress  and   original
contribution  with respect  to the first five items  as well as being
able to get a  substantial start on item   numbered six thru ten;  as
well as  doing one  of the  four items  eleven, twelve, thirteen  or
fourteen.   Finally,  our  optimistic   expectations  and  scientific
horizon lies in getting  a computer to be  able to reduce live  video
input into  a mechanical model  and to  output realistic  looking video
from a mechanical model.
6. BUDGET

	1. Baumgart
	2. A programmer.
	3. A graduate student.
	4. Two high quality display terminals.
	   e.g. Systems concept's best.